/*
   Copyright 2007 Marco Slot (marco.slot@gmail.com)

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */
package nl.marcoslot.lib.calc;

import java.util.LinkedList;
import java.util.NoSuchElementException;
import nl.marcoslot.lib.io.ParseException;

/**
 * This class provides the data structures required for the Shunting Yard algorithm
 * by Edsger Dijkstra.
 *
 * @author Marco Slot
 */
public class ShuntingYard {
    
    private LinkedList queue;
    private LinkedList stack;
    
    /**
     * Constructs a new ShuntingYard
     */
    public ShuntingYard() {
        queue = new LinkedList();
        stack = new LinkedList();
        stack.add(new OpeningParenthesis());
    }
    
    /**
     * Pops all items of the stack and appends them to the queue until an opening parenthesis is found.
     * @param c
     *    a closing parenthesis
     * @return
     *    this object
     */
    public ShuntingYard add(ClosingParenthesis c) throws ParseException {
        try {
            while(!(stack.getLast() instanceof OpeningParenthesis)) {
                queue.addLast(stack.removeLast());
            }
            stack.removeLast(); /* remove '(' */
        } catch(NoSuchElementException e) {
            throw new ParseException("Too many closing parentheses.");
        }
        return this;
    }
    
    /**
     * Adds an opening parenthesis to the stack.
     *
     * @param o
     *    an opening parenthesis
     * @return
     *    this object
     */
    public ShuntingYard add(OpeningParenthesis o) {
        stack.addLast(o);
        return this;
    }
    
    /**
     * <ol>
     * <li>While there is an operator, o2, at the top of the stack, and either
     * o1 is associative or left-associative and its precedence is less than or
     *  equal to that of o2, or o1 is right-associative and its precedence is less
     *  than that of o2, pop o2 off the stack, onto the output queue;</li>
     * <li>Adds the operator to the stack. </li>
     * </ol>
     *
     * @param o1
     *    operator to add to the stack.
     * @return
     *    this object
     */
    public ShuntingYard add(Operator o1) {
        while(!stack.isEmpty() &&
                stack.getLast() instanceof Operator &&
                (    (o1.isAssociative() || o1.isLeftAssociative()) &&  o1.compareTo(stack.getLast()) <= 0
                || (o1.isRightAssociative() && o1.compareTo(stack.getLast()) < 0) )) {
            queue.addLast(stack.removeLast());
        }
        
        stack.addLast(o1);
        
        return this;
    }
    
    /**
     * Adds a value to the queue.
     *
     * @param v
     *    the value
     * @return
     *    this object
     */
    public ShuntingYard add(Value v) {
        queue.addLast(v);
        return this;
    }
    
    /**
     * Resets the yard to its initial state and returns the Expression in Reverse Polish Notation.
     *
     * @return the expression
     * @throws java.lang.ArithmeticException
     *      If the expression is invalid. (note that the yard will be reset anyway)
     */
    public Expression close() throws ParseException {
        Expression result;
        Object[]   output;
        
        try {
            add(new ClosingParenthesis());
            
            if(stack.size() > 0) 
                throw new ParseException("Too many opening parentheses.");
            
            result = new Expression();
            output = queue.toArray();
            
            for(int i = 0; i < output.length; i++) {
                result.add(output[i]);
            }
            
            return result;
        } catch(ParseException e) {
            throw e;
        } finally {
            queue = new LinkedList();
            stack = new LinkedList();
        }
    }
}
